{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 批量梯度下降法 Batch Gradient Descent"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###    $\\nabla J(\\theta)=\\begin{pmatrix} \n",
    "    \\frac{\\partial J}{\\partial \\theta_0} \n",
    "    \\\\ \\frac{\\partial J}{\\partial \\theta_1}\n",
    "    \\\\ \\ldots\n",
    "    \\\\ \\frac{\\partial J}{\\partial \\theta_n}\n",
    "    \\end{pmatrix} = \\frac{2}{m} \n",
    "    \\begin{pmatrix}\\\\ \n",
    "    \\sum_{i=1}^{m}(X_b^{(i)}\\theta - y^{(i)})\n",
    "    \\\\ \\sum_{i=1}^{m}(X_b^{(i)}\\theta - y^{(i)}) X_1^{(i)}\n",
    "    \\\\ \\sum_{i=1}^{m}(X_b^{(i)}\\theta - y^{(i)}) X_2^{(i)}\n",
    "    \\\\ \\ldots\n",
    "    \\\\ \\sum_{i=1}^{m}(X_b^{(i)}\\theta - y^{(i)}) X_n^{(i)}\n",
    "    \\end{pmatrix} = \\frac{2}{m}\\cdot X_b^T\\cdot(X_b\\theta - y)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 随机梯度下降法 Stochastic Gradient Descent"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### $\\frac{2}{m} \n",
    "    \\begin{pmatrix}\\\\ \n",
    "    \\sum_{i=1}^{m}(X_b^{(i)}\\theta - y^{(i)})\n",
    "    \\\\ \\sum_{i=1}^{m}(X_b^{(i)}\\theta - y^{(i)}) X_1^{(i)}\n",
    "    \\\\ \\sum_{i=1}^{m}(X_b^{(i)}\\theta - y^{(i)}) X_2^{(i)}\n",
    "    \\\\ \\ldots\n",
    "    \\\\ \\sum_{i=1}^{m}(X_b^{(i)}\\theta - y^{(i)}) X_n^{(i)}\n",
    "    \\end{pmatrix}$ ----> $\\begin{pmatrix}\n",
    "(X_b^{(i)}\\theta - y^{(i)}) X_0^{(i)}\\\\ \n",
    "(X_b^{(i)}\\theta - y^{(i)}) X_1^{(i)}\\\\ \n",
    "(X_b^{(i)}\\theta - y^{(i)}) X_2^{(i)}\\\\ \n",
    "\\ldots\\\\ \n",
    "(X_b^{(i)}\\theta - y^{(i)}) X_n^{(i)}\\\\ \n",
    "\\end{pmatrix}$ $=2\\cdot (X_b^{(i)})^T\\cdot (X_b^{(i)}\\theta - y^{(i)})$ \n",
    "    \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 学习率 $\\eta = \\frac{1}{i\\_iters}$ 随着迭代次数的上升而下降(模拟退火的思想)\n",
    "#### 实际中用 $\\eta = \\frac{a}{i\\_iters\\ +\\ b}$, a和b就是随机梯度下降法中使用的超参数\n",
    "#### 经验数 a=5 , b=50"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 批量梯度下降法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "m = 100000\n",
    "\n",
    "x = np.random.normal(size=m)\n",
    "X = x.reshape(-1,1)\n",
    "y = 4.*x + 3. + np.random.normal(0, 3, size=m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def J(theta, X_b, y):\n",
    "    try:\n",
    "        return np.sum((y - X_b.dot(theta))**2)/len(y)\n",
    "    except:\n",
    "        return float('inf')\n",
    "\n",
    "def dJ(theta, X_b, y):\n",
    "    return X_b.T.dot(X_b.dot(theta) - y) * 2. / len(y)\n",
    "\n",
    "def gradient_descent(X_b, y, initial_theta, eta, n_iters=1e4, epsilon=1e-8):\n",
    "    theta = initial_theta\n",
    "    i_iter = 0\n",
    "\n",
    "    while i_iter < n_iters:\n",
    "        gradient = dJ(theta, X_b, y)\n",
    "        last_theta = theta\n",
    "        theta = theta - eta * gradient\n",
    "\n",
    "        if (abs(J(theta, X_b, y) - J(last_theta, X_b, y)) < epsilon):\n",
    "            break\n",
    "\n",
    "        i_iter += 1\n",
    "    return theta"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 1.01 s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "X_b = np.hstack([np.ones((len(X), 1)), X])\n",
    "initial_theta = np.zeros(X_b.shape[1])\n",
    "eta = 0.01\n",
    "theta = gradient_descent(X_b, y, initial_theta, eta)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([3.00506718, 4.00885108])"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "theta"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 随机梯度下降法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def dJ_sgd(theta, X_b_i, y_i):\n",
    "    return X_b_i.T.dot(X_b_i.dot(theta) - y_i) * 2."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sgd(X_b, y, initial_theta, n_iters):\n",
    "    \n",
    "    t0 = 5 # 也就是学习率的分子 a\n",
    "    t1 = 50 # 也就是学习率公式的分母 b\n",
    "    \n",
    "    def learning_rate(t):\n",
    "        return t0/(t + t1)\n",
    "    \n",
    "    theta = initial_theta\n",
    "    for cur_iter in range(n_iters):\n",
    "        rand_i = np.random.randint(len(X_b))\n",
    "        gradient = dJ_sgd(theta, X_b[rand_i], y[rand_i])\n",
    "        theta = theta - learning_rate(cur_iter)*gradient\n",
    "    \n",
    "    return theta"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 708 ms\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "X_b = np.hstack([np.ones((len(X), 1)), X])\n",
    "initial_theta = np.zeros(X_b.shape[1])\n",
    "theta = sgd(X_b, y, initial_theta, n_iters=len(X_b)//3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([2.99209387, 4.03048732])"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "theta"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 使用自己封装的随机梯度下降法训练模型"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "m = 100000\n",
    "\n",
    "x = np.random.normal(size=m)\n",
    "X = x.reshape(-1,1)\n",
    "y = 4.*x + 3. + np.random.normal(0, 3, size=m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "from c8_LinearRegression import LinearRegression"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "LinearRegression()"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lin_reg = LinearRegression()\n",
    "lin_reg.fit_sgd(X, y, n_iters=2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([3.98346802])"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lin_reg.coef_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3.000898613670543"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lin_reg.interception_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 将我们封装的随机梯度方法使用在真实数据上"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn import datasets"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "boston = datasets.load_boston()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "X = boston.data\n",
    "y = boston.target\n",
    "\n",
    "X = X[y<50.0]\n",
    "y = y[y<50.0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "from c2_model_selection import train_test_split"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "X_train, y_train, X_test, y_test = train_test_split(X, y, seed=666)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 梯度下降法, 需要 归一化 处理数据\n",
    "from sklearn.preprocessing import StandardScaler"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "standard_scaler = StandardScaler()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "standard_scaler.fit(X_train)\n",
    "X_train_standard = standard_scaler.transform(X_train)\n",
    "X_test_standard = standard_scaler.transform(X_test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "from c8_LinearRegression import LinearRegression"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "lin_Reg1 = LinearRegression()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 18 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "0.7923329555425147"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time lin_Reg1.fit_sgd(X_train_standard, y_train, n_iters=2)\n",
    "lin_Reg1.score(X_test_standard, y_test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 331 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "0.8132440489440967"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 增加迭代次数来提高训练精度\n",
    "%time lin_Reg1.fit_sgd(X_train_standard, y_train, n_iters=50)\n",
    "lin_Reg1.score(X_test_standard, y_test)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# scikit-learn中的SGD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.linear_model import SGDRegressor\n",
    "# 只能解决 线性 回归问题"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 6 ms\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "C:\\Users\\fangyang\\Anaconda3\\lib\\site-packages\\sklearn\\linear_model\\stochastic_gradient.py:128: FutureWarning: max_iter and tol parameters have been added in <class 'sklearn.linear_model.stochastic_gradient.SGDRegressor'> in 0.19. If both are left unset, they default to max_iter=5 and tol=None. If tol is not None, max_iter defaults to max_iter=1000. From 0.21, default max_iter will be 1000, and default tol will be 1e-3.\n",
      "  \"and default tol will be 1e-3.\" % type(self), FutureWarning)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "0.8045807839066259"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sgd_reg = SGDRegressor()\n",
    "%time sgd_reg.fit(X_train_standard, y_train)\n",
    "sgd_reg.score(X_test_standard, y_test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 8.99 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "0.8130817662958829"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sgd_reg = SGDRegressor(n_iter=100)\n",
    "%time sgd_reg.fit(X_train_standard, y_train)\n",
    "sgd_reg.score(X_test_standard, y_test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
